Zufallszahlen in Assembler

0 - 5:

    lda 53770
    and #5

0-23:

    lda 53770
    and #23

Mehr sollte dazu nicht nötig sein. Im Akku steht dann die gewünschte Zufallszahl.

... oder man schreibt besser gleich lda random

Hallo!

Wirklich nur AND #5 ?

Damit dürfte als Ergebnis nur 0,1,4 und 5 herauskommen, oder?

Hab es jetzt nicht getestet aber 5 sind %0101 und nur diese Kombinationen wären erlaubt:

%0000 = 0 %0001 = 1 %0100 = 4 %0101 = 5

Grüße Janko

Ja. Da habe ich zu schnell geschossen. War noch nicht ganz wach 😂

Aber mit einem CMP #6 und BCC oder BCS sollte es dann gehen

also ich mache es in MADS so:

@   mva random zufall
    #if .byte zufall>#5
    jmp @-
    #end

in zufall steht jetzt eine Zahl zwischen 0 und 5

Ein interessantes Thema mit mehr Tiefe als man denkt:

• Wie kann ich eine bestimmte (evt. sogar gleiche) Laufzeit garantieren? (Also keine Schleife, die arbeitet, bis der Wert 'passt')
• Wenn ich Werte ignoriere, ist die Verteilung noch fair? (Abgesehen davon, dass RANDOM auch nicht gleichverteilt ist, verschlechtert sich die Fairness weiter.)

Hier mal ein andere Herangehensweise:

    ; Zufallszahl von 0-5 im Akku
    ldx #0
    ldy #6
loop:
    lda RANDOM
    asl
    bcc next
    inx
next:
    dey
    bne loop

    txa

... ich hätte da auch noch einen Ansätze:

sec
lda random
sbc #95
ror
clc
ror
clc
ror
clc
ror
clc
ror

im Akkumulator steht jetzt eine Zahl zwischen 0 und 5!

ich stelle nochmal eine weitere Alternative zur Diskussion, wo die Zahlen besser verteilt sind - ist allerdings auch eine Näherung, wo die 0 etwas öfters kommt als zB die 5 … will man es gleich verteilt haben, kann man mit einer Tabelle arbeiten und die Werte von Random (0-255) auf (0-5) gleichmäßig verteilen!

Hier jetzt aber die Näherung:

lda random
ror
clc
ror
clc
ror
clc
ror
clc
inc
inc
ror
inc

Die Methode von Irgendwer gefällt mir sehr gut, jedoch je größer der Zufallszahlenbereich ist, desto länger wird die Ermittlung dauern.

Bei Peter weiß ich nicht, ob ich es richtig sehe aber "INC" ohne Parameter? Geht dass?

Grüße Janko

... ich muss zugeben, daß ich heute um ca. 4.45 aufgewacht bin und dann im Bett (im Kopf) mir diese Näherung ausgedacht habe und dann aufgestanden bin und es gepostet habe... inc geht nicht so einfach, hier müsste man wohl über die Register gehen... Die Näherung ist auch nicht besonders gut, da die 0 viel zu oft kommt!

Im Grunde ist die Lösung ja mathematisch ganz einfach: Ich habe (hoffentlich) gleich verteilte Zufallszahlen zwischen 0 und 256 - will daraus Zahlen von 0-5 machen. Also teile ich die Zufallszahlen durch 43 und schneide die Nachkommastellen ab - thats it!

In Basic wäre das so zu lösen (ich definiere jetzt mal Random als eine Zufallszahl zwischen 0-255, was ja bekanntlich in real anders in Basic ist): zufall= int(Random/43) In Zufall steht jetzt eine gleichverteilte Zufallszahl von 0-5

Das Problem ist nun allerdings: Wie teile in in Assembler eine Zahl durch 43? Das geht, ist aber echt aufwendig. Es muss also eine möglichst gut Näherung her mit folgenden Kriterien:

1. Keine Schleife
2. Die Näherung muss eine Zufallszahl durch Random generiert zwischen 0 und ca. 43 auf 0 setzen (ab ca. 43 muss dann 1 rauskommen)
3. Die gleiche Näherung muss eine Zufallszahl durch Random generiert zwischen ca. 212 und 255 auf 5 setzen.
4. Alle Bereiche dazwischen sind wohl zunächst gar nicht wichtig, denn wenn man 2. und 3. gut hinbekommt, dann werden sich die Bereiche dazwischen auch harmonisch verteilen!

Los gehts.... wer bekommt diese Näherung ohne Schleife am besten mit möglichst wenig Zyklen hin?

@Olix Mit einer Tabelle oder mit z.B. #if ... #end Abfragen bekomme ich das super verteilt von 0-255 auf 0-5 hin!

... das stimmt zwar, ist aber irrelevant, da die Wahrscheinlichkeiten für das Auftreten der Zahlen nahezu identisch ist nach Umformung. Der kleine "Rundungsfehler" geht in der normalen Ungleichverteilung der Zahlen durch den vom Rechner ebenfalls nicht gleichförmig erzeugten Zufallszahlen unter.

wenn ich z.B. die 4 mittleren Zahlen etwas häufiger anwähle bekomme ich folgende Verteilung: die 0 und die 5 kommen in 16,42% der Fälle die 1,2,3,4 kommen jeweils in 16,79% der Fälle

Olix schrieb: ... finde ich eine "sympathische " Herangehensweise, zumindest für kleinere Zufallszahlen Bereiche.

Es geht noch ein Tickchen "sympathischer" mit konstanterer Laufzeit:

    ; Zufallszahl von 0-5 im Akku
    ldy #6
    lda random
    sta tmp
    lda #0
loop:
    asl tmp 
    adc #0
    dey
    bne loop

Werden die Zahlen größer, kann man eine Kombination von direkten Interpretationen und/oder gezählten Bits nehmen. ( z.B. 23 = random & 15 + random & 7 + 1 gezähltes random bit)

... und wie machst du dann Zufallszahlen z.B. zwischen 11 und 43 ?

11 + random & 31 + ein gezähltes random bit

ok, sieht wirklich sehr eloquent aus und ist bestimmt auch relativ schnell! Da ich kein Profi bin und noch von damals aus der BASIC Ecke komme, liebe ich natürlich die schönen #if Anweisungen. Daher kommt mir auch MADS voll zugute.

Ich würde es ohne groß nachdenken zu müssen so machen (ähnlich wie oben)

zufall  .by 00
random = 53770

@   mva random zufall
    #if .byte zufall<#11 .and .byte zufall>#43
    jmp @-
    #end

... schlank und übersichtlich 😉

hmmm - ich habe jetzt mal beide Routinen getestet und beide stimmen nicht genau! Bei der Routine von irgendwer kommen bei mir Zahlen von 0-6 raus und bei der Routine von Olix kommen nur 0,1 korrekt, ansonsten kommen Sonderzeichen... Beim ersten Fall muss man ldy#5 nehmen, dann passt es...

Olix schrieb: ... geht sogar etwas kürzer und schneller:

Meine Routine ist 2 Bytes kürzer (14 Byte) und dauert zwischen 59 und 64 Zyklen (Je nachdem wie oft ein Carry auftaucht)

Falls der Kommentar im Code noch stimmen soll, musst Du noch ein Byte ("txa") hinzufügen... 😉

Irgendwer schrieb:

Olix schrieb: ... finde ich eine "sympathische " Herangehensweise, zumindest für kleinere Zufallszahlen Bereiche.

Es geht noch ein Tickchen "sympathischer" mit konstanterer Laufzeit:

; Zufallszahl von 0-5 im Akku ldy #5 lda random sta tmp lda #0 loop: asl tmp adc #0 dey bne loop

Werden die Zahlen größer, kann man eine Kombination von direkten Interpretationen und/oder gezählten Bits nehmen. ( z.B. 23 = random & 15 + random & 7 + 1 gezähltes random bit)

stimmt - mit txa geht auch der Code von Olix - hier bekomme ich aber Werte von 0-7

bei Olix Code braucht es ldy#4

Prodehl schrieb: Beim ersten Fall muss man ldy#5 nehmen, dann passt es...

Sehr gut! Danke. Theoretisch hat es funktioniert - nur praktisch nicht! 😀

ja - kleiner Fehler.. aber der Code ist echt super!!

... da ich heute ja gar nichts anderes zu tun habe (Ironie 😉 ) - habe ich das jetzt mal mehrfach getestet und muss nun leider "Euren" Ansatz komplett verwerfen!!

Bei meinem Ansatz mit der #if -Lösung kommt man für die Zahlen 0-5 auf eine recht gute prozentuale Verteilung von ca. 12% - 20%

Bei Eurem Ansatz komme ich relativ stabil auf Verteilungswerte von knapp 3% bis 33% wobei hier die Zahlen 5 und 0 auffällig unterdurchschnittlich repräsentiert werden - irgendwas stimmt hier nicht. Das sieht fast schon aus wie eine Gaußsche Normalverteilung...

.. hast du in deinem Assembler auch eine If - Option??

Moin, viele coole Routinen, aber irgendwie, ich weiß noch nicht.

Eigentlich wollen wir RANDOM mod 5 haben, also als Ergebnis etwas zwischen 0 und 4.

   lda #5
   sta modvalue

   lda RANDOM
   and #$07                 ; hier etwas grob vorfiltern, damit die Schleife nicht zu häufig rotiert.
   sec
modulus
   sbc modvalue
   bcs modulus
   adc modvalue

Im Akku steht jetzt ein Wert zwischen 0 und 4.

ok, RANDOM mod 6 und RANDOM mod 24

Aber die richtigen Werte in den Code einbinden kann jeder selbst.

Hi Lars, schöne Routine, aber die läuft nur von 0-7 Die Zufallszahl 8 kann man schon nicht mehr generieren... schade 😉

Prodehl schrieb: Bei Eurem Ansatz komme ich relativ stabil auf Verteilungswerte von knapp 3% bis 33% wobei hier die Zahlen 5 und 0 auffällig unterdurchschnittlich repräsentiert werden - irgendwas stimmt hier nicht. Das sieht fast schon aus wie eine Gaußsche Normalverteilung...

...und da hast Du vollkommen recht. Nachdem ich nochmal kurz überlegt habe, komme ich zum Schluß, dass der Ansatz nicht tauglich ist. 😳 (Aber wenigstens bin nicht nur ich darauf hereingefallen... 😀 )

Eine "Random"-Zahl binär wie 01101010 oder 10101100 ergibt in der Addition immer 4 - wenn ich jetzt nicht schon wieder einen Denkfehler habe besteht die Wahrscheinlichkeit dafür 70 zu 256 also gut 27%. Hingegen gibt es nur eine Kombination von 00000000 oder 11111111 mit der Wahrscheinlichkeit von 1/256 also knapp 0,4%.

Aber vielleicht kann man das Prinzip ja dann für Logik verwenden, bei der eine solche Gewichtung (häufige/seltene Ereignisse) von Vorteil ist...

Wenn Du größere Randomwerte brauchst, musst Du den "Vorfilter" (das AND) vergrößern.

Mögliche "Vorfilter" sind halt $03, $07, $0f, $1f, $3f, $7f. Also entsprechend immer die Bits für das AND setzen. Das könnte man auch weglassen, nur dann läuft die Schleife bei kleinen modvalue Werten halt viel länger.

Willst Du es richtig dynamisch:

; modulo im Akku vorausgesetzt:
  ldx #0
  cmp #4
  bcc ?less
  inx
  cmp #8
  bcc ?less
  inx
  cmp #16
  bcc ?less
  inx
  cmp #32
  bcc ?less
  inx
  cmp #64
  bcc ?less
  inx

?less
   lda RANDOM
   and ?filter,x         ; Vorfilter!

   sec
?modulus   
   sbc modvalue
   bcs ?modulus
   adc modvalue
   rts

?filter
 .byte $07,$0F,$1F,$3F,$7F,$FF

Ist halt etwas fummelig im Atari 2^n-1 bits für ein AND richtig zu setzen.

LG Lars

LarsImNetz schrieb: Wenn Du größere Randomwerte brauchst, musst Du den "Vorfilter" (das AND) vergrößern.

Hier gibt es IMHO aber auch ein Problem: Der Vorfilter manipuliert nämlich auch die Wahrscheinlichkeit für bestimmte Reste...

Ja, das stimmt. Aber IMHO kommt es meist darauf an recht zügig einen Random-Wert zu bekommen der in gewissen Grenzen liegt. Und mir ist es ehrlich gesagt humpe, ob er gewisse Wahrscheinlichkeiten nicht so ganz erfüllt. Hauptsache flott.

Als brauchbare Näherung reicht es für meine Zwecke völlig aus.

... mit dem größeren Vorfilter passt!

Schon cool, was man aus so einer "kleinen" Sache alles machen kann!! Was mich ein wenig stört ist allein die Tatsache, daß die meisten Ansätze die eigentlichen Random-Zahlen verändern... letztlich wartet man auf Zahlen zwischen 0-5 (oder andere Bereiche) und schneidet alles andere weg. Ob das mathematisch, statistisch korrekt ist?? 😉

Mein letzter ("toller") Ansatz behebt dieses Dilemma eindeutig:

random = 53770
zufall  .by 00
tmp .by 00

        mva random zufall

        #if .byte zufall<#43
        mva #0 tmp
        #end
        #if .byte zufall>=#43 .and .byte zufall<#86
        mva #1 tmp
        #end
        #if .byte zufall>=#86 .and .byte zufall<#128
        mva #2 tmp
        #end
        #if .byte zufall>=#128 .and .byte zufall<#170
        mva #3 tmp
        #end
        #if .byte zufall>=#170 .and .byte zufall<#212
        mva #4 tmp
        #end
        #if .byte zufall>=#212 
        mva #5 tmp
        #end

        lda tmp

Wenn man das nun umgekehrt abfragt, kann man auch deutlich kürzeren Code erzeugen...

wie würdest du das dann abfragen?

Prodehl schrieb: wie würdest du das dann abfragen?

random = 53770

                ldy #0
        lda random
                cmp #212
                bcs zero
                cmp #170
                bcs one
                cmp #128
                bcs two
                cmp #86
                bcs three
                cmp #43
                bcs four
;five
                iny
four            iny
three           iny
two             iny
one             iny
zero            tya

der Code ist chic

Super spannende Diskussion.

Hat jemand Motivation daraus einen kleinen Artikel fuer das Magazin zu machen?

... ja ich finde auch, daß die Diskussion hier mega spannend und befruchtend ist! Was man alles lernen kann...

Wenn sich keine findet, würde ich daraus einen kleinen Artikel machen und das von 0-5 auf 0-7 erweitern, da man dann noch einen anderen Ansatz diskutieren könnt 😉

Aber wie gesagt, wenn jemand anderes das Thema gerne präsentieren möchte - gerne!!

Hi,

ich muß ehrlich gestehen, daß ich nie gedacht hätte, daß das Generieren einer Zufallszahl in Assembler so schwierig ist.

Einige der angedachten Lösungen funktionieren nicht oder nicht richtig, ein weiterer Teil ist handgeschnitzt auf den zu erzielenden Wertebereich und den größten Teil hab ich auf die Schnelle beim Durchlesen nicht mal verstanden.

Ich wäre vermutlich sehr faul gewesen und hätte es eher wie in BASIC gemacht und einfach die Fließkommaroutinen verwendet und dann sowas wie MAXZAHL*RANDOM/255.

Von den benötigten Zyklen sprengt das natürlich jeden Rahmen und ist für die Verwendung innerhalb zeitkritischer Operationen völlig untauglich.

Dann hab ich gerade noch überlegt, daß Integer Multiplikation und Division beschränkt auf 16 Bit ja schneller sein müßte als FP. Aber allein die Erläuterung der bestehenden Algorithmen ist so abschreckend abgehoben - ne danke.

Vielleicht könnte man für Dezimalzahlen mit wenigen stellen sowas machen:

Man nehme einen zehnseitigen Würfel (0-9). Den würfelt man für jede Dezimalstelle und setzt aus den Ergebnissen die Zahl zusammen. Die Routine für 0-9 wäre dann fix. Nachteilig wäre, daß pro Dezimalstelle ein zusätzlicher Durchlauf benötigt wird und daß vielleicht eine Routine abschließend führende Nullen ausblenden muß.

Da fällt mir gerade auf: gewünscht waren ja eine Zufallszahl von 0-5 oder eine mit max 23. Das geht mit so einem zehnseitigen Würfel auch wieder nicht.

Bin echt gespannt, wie es in dem Thema weiter geht.

CU, Erhard

... ich werde in den nächsten Tagen noch einen weiteren Ansatz hier posten. Theoretisch mathematisch recht einfach und oben schon angedeutet will ich die Zufallszahl von 0-255 - also das, was RANDOM ausgibt durch 43 teilen. Warum 43? die 43 steckt 5,93 mal in 255 drin - also bekomme ich durchs teilen Werte zwischen 0 und 5,9 und das auch ganz gleichmäßig verteilt! Nun ist teilen in Assembler ja bekanntlich nicht so einfach, aber wir haben ja einen Computer! Teilen einer Zahl a durch eine andere Zahl b ist ja nichts anderes, als von a solange b abzuziehen, bis wir 0 oder kleiner bekommen. Wenn ich also von der Zufallszahl 43 subtrahiere und direkt in einen Minusbereich komme (Overflow), dann ist die Routine schon fertig und wir bekommen das Ergebnis 0 . Wenn kein Overflow subtrahieren wir weiter, erhöhen das Ergebnis jeweils um 1 bis der Overflow kommt. Relativ einfach also.... daraus kann man eine feine kleine Routine machen. Braucht man höhere Zahlen, teilt man nicht durch 43, sondern durch kleine Zahlen...

Gruß Peter

na gut... hab es gleich gemacht 😉

        lda #43 
        sta tmp

        ldx #0
        lda random
        sbc tmp
        bvs exit
        inx
        sbc tmp
        bvs exit
        inx
        sbc tmp
        bvs exit
        inx
        sbc tmp
        bvs exit
        inx
        sbc tmp
        bvs exit
        inx     
    exit    txa

hier noch etwas schlanker angepasst:

        ldx #255
        lda 53770
        sec
lp      inx
        sbc #43
        bcs lp
        txa

Vorsicht: Das Overflow-Flag ist für Arithmetik im Zweier-Komplement (Zahlenbereich von -128 bis +127) vorgesehen. Daher funktioniert das so im allgemeinen nicht. Beispiel: Nach lda #129 : sec : sbc #2 ist das Overflow-Flag gesetzt, da 129 im Zweier-Komplement -127 entspricht und wenn man da noch 2 abzieht, kommen wir auf -129, was nicht mehr im Zweier-Komplement darstellbar ist, d.h. die CPU setzt das Overflow-Flag.

Ersetze einfach bvc durch bcs, dann klappt es, da nun das Carry-Flag entscheidet (ist auch eine Art Overflow, aber im Bereich 0 bis 255, was hier ja gewünscht ist).

... ich habe das gerade mal mit bcs getestet und entsprechend den Code geändert! Danke für den Hinweis! Ich hatte mich beim testen auch schon über komische Effekte bei höheren Subtraktionen gewundert ab 128 😉

Mit den ganzen branch-Befehlen bin ich noch nicht so im Detail auf du-und-du - da muss ich noch nachlegen, dann kann ich in kritischen Programmteilen auch besser und sinnvoller meine #if Anweisungen reduzieren!

Ja, ich hatte damals (vor knapp 40 Jahren) auch etwas gebraucht, bis ich das verstanden hatte - war eine spannende Zeit damals. 🙂

Die wichtigsten Branch-Befehle sind BEQ und BNE (oft in Verbindung mit CMP/CPY/CPX), dann BCC und BCS (ebenso und mit ADC/SBC), dann mit Abstand BPL und BMI (meist für kurze Schleifen mit 0-Durchlauf: ldy #6 : loop ... dey : bpl loop, das zählt Y von 6 bis 0 einschließlich). BVC und BVS benutze ich nur höchst selten (fast nur in Verbindung mit BIT, um Bit #6 zu testen).

@Dietrich, vielleicht sollten wir für das Thema lda/cmp/bxx ein neues Thema öffnen?

super Idee